README.md

91. Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26 

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). 

Example 2:

Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). 

Solutions (Python)

1. Dynamic Programming

classSolution: defnumDecodings(self, s: str) ->int: ifs[0] =='0': return0prev, curr=1, 1foriinrange(1, len(s)): ifs[i] =='0'and (s[i-1] >'2'ors[i-1] =='0'): return0elifs[i] =='0': curr=prevelif"10"<s[i-1:i+1] <"27": prev, curr=curr, prev+currelse: prev=currreturncurr

Solutions (Ruby)

1. Dynamic Programming

# @param {String} s# @return {Integer}defnum_decodings(s)return0ifs[0] == '0'prev,curr=1,1foriin1...s.lengthifs[i] == '0'and(s[i - 1] > '2'ors[i - 1] == '0')return0elsifs[i] == '0'curr=prevelsifs[i - 1..i] > "10"ands[i - 1..i] < "27"prev,curr=curr,prev + currelseprev=currendendreturncurrend